home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / nn.zip / REGEXP.C < prev    next >
C/C++ Source or Header  |  1989-06-28  |  31KB  |  1,333 lines
  1. /*
  2.  * regexp.c - regular expression matching
  3.  *
  4.  * NOTICE: THIS CODE HAS BEEN MODIFIED TO FIT THE NN ENVIRONMENT.
  5.  *
  6.  * DESCRIPTION
  7.  *
  8.  *    This source was taken from the pax posting in comp.sources.unix.
  9.  *
  10.  *    Underneath the reformatting and comment blocks which were added to 
  11.  *    make it consistent with the rest of the code, you will find a
  12.  *    modified version of Henry Specer's regular expression library.
  13.  *    Henry's functions were modified to provide the minimal regular
  14.  *    expression matching, as required by P1003.  Henry's code was
  15.  *    copyrighted, and copy of the copyright message and restrictions
  16.  *    are provided, verbatim, below:
  17.  *
  18.  *    Copyright (c) 1986 by University of Toronto.
  19.  *    Written by Henry Spencer.  Not derived from licensed software.
  20.  *
  21.  *    Permission is granted to anyone to use this software for any
  22.  *    purpose on any computer system, and to redistribute it freely,
  23.  *    subject to the following restrictions:
  24.  *
  25.  *    1. The author is not responsible for the consequences of use of
  26.  *         this software, no matter how awful, even if they arise
  27.  *       from defects in it.
  28.  *
  29.  *    2. The origin of this software must not be misrepresented, either
  30.  *       by explicit claim or by omission.
  31.  *
  32.  *    3. Altered versions must be plainly marked as such, and must not
  33.  *       be misrepresented as being the original software.
  34.  *
  35.  *     Beware that some of this code is subtly aware of the way operator
  36.  *     precedence is structured in regular expressions.  Serious changes in
  37.  *     regular-expression syntax might require a total rethink.
  38.  *
  39.  * AUTHORS
  40.  *
  41.  *     Mark H. Colburn, NAPS International (mark@jhereg.mn.org)
  42.  *     Henry Spencer, University of Torronto (henry@utzoo.edu)
  43.  *
  44.  * Sponsored by The USENIX Association for public distribution. 
  45.  *
  46.  * $Log:    regexp.c,v $
  47.  * Revision 1.1  88/12/23  18:02:32  mark
  48.  * Initial revision
  49.  * 
  50.  */
  51.  
  52. #define NN
  53.  
  54. /* Headers */
  55.  
  56. #ifdef NN
  57. #include "config.h"
  58. #include "regexp.h"
  59. #else
  60. #include "pax.h"
  61.  
  62. #ifndef lint
  63. static char    *Ident = "$Id: regexp.c,v 1.1 88/12/23 18:02:32 mark Rel $";
  64. #endif
  65. #endif
  66.  
  67. /*
  68.  * The "internal use only" fields in regexp.h are present to pass info from
  69.  * compile to execute that permits the execute phase to run lots faster on
  70.  * simple cases.  They are:
  71.  *
  72.  * regstart    char that must begin a match; '\0' if none obvious
  73.  * reganch    is the match anchored (at beginning-of-line only)?
  74.  * regmust    string (pointer into program) that match must include, or NULL
  75.  * regmlen    length of regmust string
  76.  *
  77.  * Regstart and reganch permit very fast decisions on suitable starting points
  78.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  79.  * of lines that cannot possibly match.  The regmust tests are costly enough
  80.  * that regcomp() supplies a regmust only if the r.e. contains something
  81.  * potentially expensive (at present, the only such thing detected is * or +
  82.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  83.  * supplied because the test in regexec() needs it and regcomp() is computing
  84.  * it anyway.
  85.  */
  86.  
  87. /*
  88.  * Structure for regexp "program".  This is essentially a linear encoding
  89.  * of a nondeterministic finite-state machine (aka syntax charts or
  90.  * "railroad normal form" in parsing technology).  Each node is an opcode
  91.  * plus a "nxt" pointer, possibly plus an operand.  "Nxt" pointers of
  92.  * all nodes except BRANCH implement concatenation; a "nxt" pointer with
  93.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  94.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  95.  * opposed to a collection of them) is never concatenated with anything
  96.  * because of operator precedence.)  The operand of some types of node is
  97.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  98.  * particular, the operand of a BRANCH node is the first node of the branch.
  99.  * (NB this is *not* a tree structure:  the tail of the branch connects
  100.  * to the thing following the set of BRANCHes.)  The opcodes are:
  101.  */
  102.  
  103. /* definition    number    opnd?    meaning */
  104. #define    END    0        /* no    End of program. */
  105. #define    BOL    1        /* no    Match "" at beginning of line. */
  106. #define    EOL    2        /* no    Match "" at end of line. */
  107. #define    ANY    3        /* no    Match any one character. */
  108. #define    ANYOF    4        /* str    Match any character in this string. */
  109. #define    ANYBUT    5        /* str    Match any character not in this
  110.                  * string. */
  111. #define    BRANCH    6        /* node    Match this alternative, or the
  112.                  * nxt... */
  113. #define    BACK    7        /* no    Match "", "nxt" ptr points backward. */
  114. #define    EXACTLY    8        /* str    Match this string. */
  115. #define    NOTHING    9        /* no    Match empty string. */
  116. #define    STAR    10        /* node    Match this (simple) thing 0 or more
  117.                  * times. */
  118. #define    OPEN    20        /* no    Mark this point in input as start of
  119.                  * #n. */
  120.  /* OPEN+1 is number 1, etc. */
  121. #define    CLOSE    30        /* no    Analogous to OPEN. */
  122.  
  123. /*
  124.  * Opcode notes:
  125.  *
  126.  * BRANCH    The set of branches constituting a single choice are hooked
  127.  *        together with their "nxt" pointers, since precedence prevents
  128.  *        anything being concatenated to any individual branch.  The
  129.  *        "nxt" pointer of the last BRANCH in a choice points to the
  130.  *        thing following the whole choice.  This is also where the
  131.  *        final "nxt" pointer of each individual branch points; each
  132.  *        branch starts with the operand node of a BRANCH node.
  133.  *
  134.  * BACK        Normal "nxt" pointers all implicitly point forward; BACK
  135.  *        exists to make loop structures possible.
  136.  *
  137.  * STAR        complex '*', are implemented as circular BRANCH structures 
  138.  *        using BACK.  Simple cases (one character per match) are 
  139.  *        implemented with STAR for speed and to minimize recursive 
  140.  *        plunges.
  141.  *
  142.  * OPEN,CLOSE    ...are numbered at compile time.
  143.  */
  144.  
  145. /*
  146.  * A node is one char of opcode followed by two chars of "nxt" pointer.
  147.  * "Nxt" pointers are stored as two 8-bit pieces, high order first.  The
  148.  * value is a positive offset from the opcode of the node containing it.
  149.  * An operand, if any, simply follows the node.  (Note that much of the
  150.  * code generation knows about this implicit relationship.)
  151.  *
  152.  * Using two bytes for the "nxt" pointer is vast overkill for most things,
  153.  * but allows patterns to get big without disasters.
  154.  */
  155. #define    OP(p)    (*(p))
  156. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  157. #define    OPERAND(p)    ((p) + 3)
  158.  
  159. /*
  160.  * Utility definitions.
  161.  */
  162.  
  163. #define    FAIL(m)    { regerror(m); return(NULL); }
  164. #define    ISMULT(c)    ((c) == '*')
  165. #define    META    "^$.[()|*\\"
  166. #ifndef CHARBITS
  167. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  168. #else
  169. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  170. #endif
  171.  
  172. /*
  173.  * Flags to be passed up and down.
  174.  */
  175. #define    HASWIDTH    01    /* Known never to match null string. */
  176. #define    SIMPLE        02    /* Simple enough to be STAR operand. */
  177. #define    SPSTART        04    /* Starts with * */
  178. #define    WORST        0    /* Worst case. */
  179.  
  180. /*
  181.  * Global work variables for regcomp().
  182.  */
  183. static char    *regparse;    /* Input-scan pointer. */
  184. static int      regnpar;    /* () count. */
  185. static char     regdummy;
  186. static char    *regcode;    /* Code-emit pointer; ®dummy = don't. */
  187. static long     regsize;    /* Code size. */
  188.  
  189. /*
  190.  * Forward declarations for regcomp()'s friends.
  191.  */
  192. #ifndef STATIC
  193. #define    STATIC    static
  194. #endif
  195. STATIC char    *reg();
  196. STATIC char    *regbranch();
  197. STATIC char    *regpiece();
  198. STATIC char    *regatom();
  199. STATIC char    *regnode();
  200. STATIC char    *regnext();
  201. STATIC void     regc();
  202. STATIC void     reginsert();
  203. STATIC void     regtail();
  204. STATIC void     regoptail();
  205. #ifdef STRCSPN
  206. STATIC int      strcspn();
  207. #endif
  208.  
  209. /*
  210.  - regcomp - compile a regular expression into internal code
  211.  *
  212.  * We can't allocate space until we know how big the compiled form will be,
  213.  * but we can't compile it (and thus know how big it is) until we've got a
  214.  * place to put the code.  So we cheat:  we compile it twice, once with code
  215.  * generation turned off and size counting turned on, and once "for real".
  216.  * This also means that we don't allocate space until we are sure that the
  217.  * thing really will compile successfully, and we never have to move the
  218.  * code and thus invalidate pointers into it.  (Note that it has to be in
  219.  * one piece because free() must be able to free it all.)
  220.  *
  221.  * Beware that the optimization-preparation code in here knows about some
  222.  * of the structure of the compiled regexp.
  223.  */
  224. regexp *regcomp(exp)
  225. char           *exp;
  226. {
  227.     register regexp *r;
  228.     register char  *scan;
  229.     register char  *longest;
  230.     register int    len;
  231.     int             flags;
  232.     extern char    *malloc();
  233.  
  234.     if (exp == NULL)
  235.     FAIL("NULL argument");
  236.  
  237.     /* First pass: determine size, legality. */
  238.     regparse = exp;
  239.     regnpar = 1;
  240.     regsize = 0L;
  241.     regcode = ®dummy;
  242.     regc(MAGIC);
  243.     if (reg(0, &flags) == NULL)
  244.     return (NULL);
  245.  
  246.     /* Small enough for pointer-storage convention? */
  247.     if (regsize >= 32767L)    /* Probably could be 65535L. */
  248.     FAIL("regexp too big");
  249.  
  250.     /* Allocate space. */
  251.     r = (regexp *) malloc(sizeof(regexp) + (unsigned) regsize);
  252.     if (r == NULL)
  253.     FAIL("out of space");
  254.  
  255.     /* Second pass: emit code. */
  256.     regparse = exp;
  257.     regnpar = 1;
  258.     regcode = r->program;
  259.     regc(MAGIC);
  260.     if (reg(0, &flags) == NULL)
  261.     return (NULL);
  262.  
  263.     /* Dig out information for optimizations. */
  264.     r->regstart = '\0';        /* Worst-case defaults. */
  265.     r->reganch = 0;
  266.     r->regmust = NULL;
  267.     r->regmlen = 0;
  268.     scan = r->program + 1;    /* First BRANCH. */
  269.     if (OP(regnext(scan)) == END) {    /* Only one top-level choice. */
  270.     scan = OPERAND(scan);
  271.  
  272.     /* Starting-point info. */
  273.     if (OP(scan) == EXACTLY)
  274.         r->regstart = *OPERAND(scan);
  275.     else if (OP(scan) == BOL)
  276.         r->reganch++;
  277.  
  278.     /*
  279.      * If there's something expensive in the r.e., find the longest
  280.      * literal string that must appear and make it the regmust.  Resolve
  281.      * ties in favor of later strings, since the regstart check works
  282.      * with the beginning of the r.e. and avoiding duplication
  283.      * strengthens checking.  Not a strong reason, but sufficient in the
  284.      * absence of others. 
  285.      */
  286.     if (flags & SPSTART) {
  287.         longest = NULL;
  288.         len = 0;
  289.         for (; scan != NULL; scan = regnext(scan))
  290.         if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  291.             longest = OPERAND(scan);
  292.             len = strlen(OPERAND(scan));
  293.         }
  294.         r->regmust = longest;
  295.         r->regmlen = len;
  296.     }
  297.     }
  298.     return (r);
  299. }
  300.  
  301. /*
  302.  - reg - regular expression, i.e. main body or parenthesized thing
  303.  *
  304.  * Caller must absorb opening parenthesis.
  305.  *
  306.  * Combining parenthesis handling with the base level of regular expression
  307.  * is a trifle forced, but the need to tie the tails of the branches to what
  308.  * follows makes it hard to avoid.
  309.  */
  310. static char *reg(paren, flagp)
  311. int             paren;        /* Parenthesized? */
  312. int            *flagp;
  313. {
  314.     register char  *ret;
  315.     register char  *br;
  316.     register char  *ender;
  317.     register int    parno;
  318.     int             flags;
  319.  
  320.     *flagp = HASWIDTH;        /* Tentatively. */
  321.  
  322.     /* Make an OPEN node, if parenthesized. */
  323.     if (paren) {
  324.     if (regnpar >= NSUBEXP)
  325.         FAIL("too many ()");
  326.     parno = regnpar;
  327.     regnpar++;
  328.     ret = regnode(OPEN + parno);
  329.     } else
  330.     ret = NULL;
  331.  
  332.     /* Pick up the branches, linking them together. */
  333.     br = regbranch(&flags);
  334.     if (br == NULL)
  335.     return (NULL);
  336.     if (ret != NULL)
  337.     regtail(ret, br);    /* OPEN -> first. */
  338.     else
  339.     ret = br;
  340.     if (!(flags & HASWIDTH))
  341.     *flagp &= ~HASWIDTH;
  342.     *flagp |= flags & SPSTART;
  343.     while (*regparse == '|') {
  344.     regparse++;
  345.     br = regbranch(&flags);
  346.     if (br == NULL)
  347.         return (NULL);
  348.     regtail(ret, br);    /* BRANCH -> BRANCH. */
  349.     if (!(flags & HASWIDTH))
  350.         *flagp &= ~HASWIDTH;
  351.     *flagp |= flags & SPSTART;
  352.     }
  353.  
  354.     /* Make a closing node, and hook it on the end. */
  355.     ender = regnode((paren) ? CLOSE + parno : END);
  356.     regtail(ret, ender);
  357.  
  358.     /* Hook the tails of the branches to the closing node. */
  359.     for (br = ret; br != NULL; br = regnext(br))
  360.     regoptail(br, ender);
  361.  
  362.     /* Check for proper termination. */
  363.     if (paren && *regparse++ != ')') {
  364.     FAIL("unmatched ()");
  365.     } else if (!paren && *regparse != '\0') {
  366.     if (*regparse == ')') {
  367.         FAIL("unmatched ()");
  368.     } else
  369.         FAIL("junk on end");/* "Can't happen". */
  370.     /* NOTREACHED */
  371.     }
  372.     return (ret);
  373. }
  374.  
  375. /*
  376.  - regbranch - one alternative of an | operator
  377.  *
  378.  * Implements the concatenation operator.
  379.  */
  380. static char  *regbranch(flagp)
  381. int            *flagp;
  382. {
  383.     register char  *ret;
  384.     register char  *chain;
  385.     register char  *latest;
  386.     int             flags;
  387.  
  388.     *flagp = WORST;        /* Tentatively. */
  389.  
  390.     ret = regnode(BRANCH);
  391.     chain = NULL;
  392.     while (*regparse != '\0' && *regparse != '|' && *regparse != ')') {
  393.     latest = regpiece(&flags);
  394.     if (latest == NULL)
  395.         return (NULL);
  396.     *flagp |= flags & HASWIDTH;
  397.     if (chain == NULL)    /* First piece. */
  398.         *flagp |= flags & SPSTART;
  399.     else
  400.         regtail(chain, latest);
  401.     chain = latest;
  402.     }
  403.     if (chain == NULL)        /* Loop ran zero times. */
  404.     regnode(NOTHING);
  405.  
  406.     return (ret);
  407. }
  408.  
  409. /*
  410.  - regpiece - something followed by possible [*]
  411.  *
  412.  * Note that the branching code sequence used for * is somewhat optimized:  
  413.  * they use the same NOTHING node as both the endmarker for their branch 
  414.  * list and the body of the last branch.  It might seem that this node could 
  415.  * be dispensed with entirely, but the endmarker role is not redundant.
  416.  */
  417. static char *regpiece(flagp)
  418. int            *flagp;
  419. {
  420.     register char  *ret;
  421.     register char   op;
  422.     register char  *nxt;
  423.     int             flags;
  424.  
  425.     ret = regatom(&flags);
  426.     if (ret == NULL)
  427.     return (NULL);
  428.  
  429.     op = *regparse;
  430.     if (!ISMULT(op)) {
  431.     *flagp = flags;
  432.     return (ret);
  433.     }
  434.     if (!(flags & HASWIDTH))
  435.     FAIL("* operand could be empty");
  436.     *flagp = (WORST | SPSTART);
  437.  
  438.     if (op == '*' && (flags & SIMPLE))
  439.     reginsert(STAR, ret);
  440.     else if (op == '*') {
  441.     /* Emit x* as (x&|), where & means "self". */
  442.     reginsert(BRANCH, ret);    /* Either x */
  443.     regoptail(ret, regnode(BACK));    /* and loop */
  444.     regoptail(ret, ret);    /* back */
  445.     regtail(ret, regnode(BRANCH));    /* or */
  446.     regtail(ret, regnode(NOTHING));    /* null. */
  447.     } 
  448.     regparse++;
  449.     if (ISMULT(*regparse))
  450.     FAIL("nested *");
  451.  
  452.     return (ret);
  453. }
  454.  
  455. /*
  456.  - regatom - the lowest level
  457.  *
  458.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  459.  * it can turn them into a single node, which is smaller to store and
  460.  * faster to run.  Backslashed characters are exceptions, each becoming a
  461.  * separate node; the code is simpler that way and it's not worth fixing.
  462.  */
  463. static char *regatom(flagp)
  464. int            *flagp;
  465. {
  466.     register char  *ret;
  467.     int             flags;
  468.  
  469.     *flagp = WORST;        /* Tentatively. */
  470.  
  471.     switch (*regparse++) {
  472.     case '^':
  473.     ret = regnode(BOL);
  474.     break;
  475.     case '$':
  476.     ret = regnode(EOL);
  477.     break;
  478.     case '.':
  479.     ret = regnode(ANY);
  480.     *flagp |= HASWIDTH | SIMPLE;
  481.     break;
  482.     case '[':{
  483.         register int    class;
  484.         register int    classend;
  485.  
  486.         if (*regparse == '^') {    /* Complement of range. */
  487.         ret = regnode(ANYBUT);
  488.         regparse++;
  489.         } else
  490.         ret = regnode(ANYOF);
  491.         if (*regparse == ']' || *regparse == '-')
  492.         regc(*regparse++);
  493.         while (*regparse != '\0' && *regparse != ']') {
  494.         if (*regparse == '-') {
  495.             regparse++;
  496.             if (*regparse == ']' || *regparse == '\0')
  497.             regc('-');
  498.             else {
  499.             class = UCHARAT(regparse - 2) + 1;
  500.             classend = UCHARAT(regparse);
  501.             if (class > classend + 1)
  502.                 FAIL("invalid [] range");
  503.             for (; class <= classend; class++)
  504.                 regc(class);
  505.             regparse++;
  506.             }
  507.         } else
  508.             regc(*regparse++);
  509.         }
  510.         regc('\0');
  511.         if (*regparse != ']')
  512.         FAIL("unmatched []");
  513.         regparse++;
  514.         *flagp |= HASWIDTH | SIMPLE;
  515.     }
  516.     break;
  517.     case '(':
  518.     ret = reg(1, &flags);
  519.     if (ret == NULL)
  520.         return (NULL);
  521.     *flagp |= flags & (HASWIDTH | SPSTART);
  522.     break;
  523.     case '\0':
  524.     case '|':
  525.     case ')':
  526.     FAIL("internal urp");    /* Supposed to be caught earlier. */
  527.     break;
  528.     case '*':
  529.     FAIL("* follows nothing");
  530.     break;
  531.     case '\\':
  532.     if (*regparse == '\0')
  533.         FAIL("trailing \\");
  534.     ret = regnode(EXACTLY);
  535.     regc(*regparse++);
  536.     regc('\0');
  537.     *flagp |= HASWIDTH | SIMPLE;
  538.     break;
  539.     default:{
  540.         register int    len;
  541.         register char   ender;
  542.  
  543.         regparse--;
  544.         len = strcspn(regparse, META);
  545.         if (len <= 0)
  546.         FAIL("internal disaster");
  547.         ender = *(regparse + len);
  548.         if (len > 1 && ISMULT(ender))
  549.         len--;        /* Back off clear of * operand. */
  550.         *flagp |= HASWIDTH;
  551.         if (len == 1)
  552.         *flagp |= SIMPLE;
  553.         ret = regnode(EXACTLY);
  554.         while (len > 0) {
  555.         regc(*regparse++);
  556.         len--;
  557.         }
  558.         regc('\0');
  559.     }
  560.     break;
  561.     }
  562.  
  563.     return (ret);
  564. }
  565.  
  566. /*
  567.  - regnode - emit a node
  568.  */
  569. static char *regnode(op)
  570. char            op;
  571. {
  572.     register char  *ret;
  573.     register char  *ptr;
  574.  
  575.     ret = regcode;
  576.     if (ret == ®dummy) {
  577.     regsize += 3;
  578.     return (ret);
  579.     }
  580.     ptr = ret;
  581.     *ptr++ = op;
  582.     *ptr++ = '\0';        /* Null "nxt" pointer. */
  583.     *ptr++ = '\0';
  584.     regcode = ptr;
  585.  
  586.     return (ret);
  587. }
  588.  
  589. /*
  590.  - regc - emit (if appropriate) a byte of code
  591.  */
  592. static void regc(b)
  593. char            b;
  594. {
  595.     if (regcode != ®dummy)
  596.     *regcode++ = b;
  597.     else
  598.     regsize++;
  599. }
  600.  
  601. /*
  602.  - reginsert - insert an operator in front of already-emitted operand
  603.  *
  604.  * Means relocating the operand.
  605.  */
  606. static void reginsert(op, opnd)
  607. char            op;
  608. char           *opnd;
  609. {
  610.     register char  *src;
  611.     register char  *dst;
  612.     register char  *place;
  613.  
  614.     if (regcode == ®dummy) {
  615.     regsize += 3;
  616.     return;
  617.     }
  618.     src = regcode;
  619.     regcode += 3;
  620.     dst = regcode;
  621.     while (src > opnd)
  622.     *--dst = *--src;
  623.  
  624.     place = opnd;        /* Op node, where operand used to be. */
  625.     *place++ = op;
  626.     *place++ = '\0';
  627.     *place++ = '\0';
  628. }
  629.  
  630. /*
  631.  - regtail - set the next-pointer at the end of a node chain
  632.  */
  633. static void regtail(p, val)
  634. char           *p;
  635. char           *val;
  636. {
  637.     register char  *scan;
  638.     register char  *temp;
  639.     register int    offset;
  640.  
  641.     if (p == ®dummy)
  642.     return;
  643.  
  644.     /* Find last node. */
  645.     scan = p;
  646.     for (;;) {
  647.     temp = regnext(scan);
  648.     if (temp == NULL)
  649.         break;
  650.     scan = temp;
  651.     }
  652.  
  653.     if (OP(scan) == BACK)
  654.     offset = scan - val;
  655.     else
  656.     offset = val - scan;
  657.     *(scan + 1) = (offset >> 8) & 0377;
  658.     *(scan + 2) = offset & 0377;
  659. }
  660.  
  661. /*
  662.  - regoptail - regtail on operand of first argument; nop if operandless
  663.  */
  664. static void regoptail(p, val)
  665. char           *p;
  666. char           *val;
  667. {
  668.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  669.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  670.     return;
  671.     regtail(OPERAND(p), val);
  672. }
  673.  
  674. /*
  675.  * regexec and friends
  676.  */
  677.  
  678. /*
  679.  * Global work variables for regexec().
  680.  */
  681. static char    *reginput;    /* String-input pointer. */
  682. static char    *regbol;        /* Beginning of input, for ^ check. */
  683. static char   **regstartp;    /* Pointer to startp array. */
  684. static char   **regendp;    /* Ditto for endp. */
  685.  
  686. /*
  687.  * Forwards.
  688.  */
  689. STATIC int      regtry();
  690. STATIC int      regmatch();
  691. STATIC int      regrepeat();
  692.  
  693. #ifdef DEBUG
  694. int             regnarrate = 0;
  695. void            regdump();
  696. STATIC char    *regprop();
  697. #endif
  698.  
  699. /*
  700.  - regexec - match a regexp against a string
  701.  */
  702. int regexec(prog, string)
  703. register regexp *prog;
  704. register char  *string;
  705. {
  706.     register char  *s;
  707.  
  708.     /* Be paranoid... */
  709.     if (prog == NULL || string == NULL) {
  710.     regerror("NULL parameter");
  711.     return (0);
  712.     }
  713.     /* Check validity of program. */
  714.     if (UCHARAT(prog->program) != MAGIC) {
  715.     regerror("corrupted program");
  716.     return (0);
  717.     }
  718.     /* If there is a "must appear" string, look for it. */
  719.     if (prog->regmust != NULL) {
  720.     s = string;
  721.     while ((s = strchr(s, prog->regmust[0])) != NULL) {
  722.         if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  723.         break;        /* Found it. */
  724.         s++;
  725.     }
  726.     if (s == NULL)        /* Not present. */
  727.         return (0);
  728.     }
  729.     /* Mark beginning of line for ^ . */
  730.     regbol = string;
  731.  
  732.     /* Simplest case:  anchored match need be tried only once. */
  733.     if (prog->reganch)
  734.     return (regtry(prog, string));
  735.  
  736.     /* Messy cases:  unanchored match. */
  737.     s = string;
  738.     if (prog->regstart != '\0')
  739.     /* We know what char it must start with. */
  740.     while ((s = strchr(s, prog->regstart)) != NULL) {
  741.         if (regtry(prog, s))
  742.         return (1);
  743.         s++;
  744.     }
  745.     else
  746.     /* We don't -- general case. */
  747.     do {
  748.         if (regtry(prog, s))
  749.         return (1);
  750.     } while (*s++ != '\0');
  751.  
  752.     /* Failure. */
  753.     return (0);
  754. }
  755.  
  756. /*
  757.  - regtry - try match at specific point
  758.  */
  759. #ifdef __STDC__
  760.  
  761. static int regtry(regexp *prog, char *string)
  762.  
  763. #else
  764.  
  765. static int regtry(prog, string)
  766. regexp         *prog;
  767. char           *string;
  768.  
  769. #endif
  770. {
  771.     register int    i;
  772.     register char **sp;
  773.     register char **ep;
  774.  
  775.     reginput = string;
  776.     regstartp = prog->startp;
  777.     regendp = prog->endp;
  778.  
  779.     sp = prog->startp;
  780.     ep = prog->endp;
  781.     for (i = NSUBEXP; i > 0; i--) {
  782.     *sp++ = NULL;
  783.     *ep++ = NULL;
  784.     }
  785.     if (regmatch(prog->program + 1)) {
  786.     prog->startp[0] = string;
  787.     prog->endp[0] = reginput;
  788.     return (1);
  789.     } else
  790.     return (0);
  791. }
  792.  
  793. /*
  794.  - regmatch - main matching routine
  795.  *
  796.  * Conceptually the strategy is simple:  check to see whether the current
  797.  * node matches, call self recursively to see whether the rest matches,
  798.  * and then act accordingly.  In practice we make some effort to avoid
  799.  * recursion, in particular by going through "ordinary" nodes (that don't
  800.  * need to know whether the rest of the match failed) by a loop instead of
  801.  * by recursion.
  802.  */
  803. #ifdef __STDC__
  804.  
  805. static int regmatch(char *prog)
  806.  
  807. #else
  808.  
  809. static int regmatch(prog)
  810. char           *prog;
  811.  
  812. #endif
  813. {
  814.     register char  *scan;    /* Current node. */
  815.     char           *nxt;    /* nxt node. */
  816.  
  817.     scan = prog;
  818. #ifdef DEBUG
  819.     if (scan != NULL && regnarrate)
  820.     fprintf(stderr, "%s(\n", regprop(scan));
  821. #endif
  822.     while (scan != NULL) {
  823. #ifdef DEBUG
  824.     if (regnarrate)
  825.         fprintf(stderr, "%s...\n", regprop(scan));
  826. #endif
  827.     nxt = regnext(scan);
  828.  
  829.     switch (OP(scan)) {
  830.     case BOL:
  831.         if (reginput != regbol)
  832.         return (0);
  833.         break;
  834.     case EOL:
  835.         if (*reginput != '\0')
  836.         return (0);
  837.         break;
  838.     case ANY:
  839.         if (*reginput == '\0')
  840.         return (0);
  841.         reginput++;
  842.         break;
  843.     case EXACTLY:{
  844.         register int    len;
  845.         register char  *opnd;
  846.  
  847.         opnd = OPERAND(scan);
  848.         /* Inline the first character, for speed. */
  849.         if (*opnd != *reginput)
  850.             return (0);
  851.         len = strlen(opnd);
  852.         if (len > 1 && strncmp(opnd, reginput, len) != 0)
  853.             return (0);
  854.         reginput += len;
  855.         }
  856.         break;
  857.     case ANYOF:
  858.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  859.         return (0);
  860.         reginput++;
  861.         break;
  862.     case ANYBUT:
  863.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  864.         return (0);
  865.         reginput++;
  866.         break;
  867.     case NOTHING:
  868.         break;
  869.     case BACK:
  870.         break;
  871.     case OPEN + 1:
  872.     case OPEN + 2:
  873.     case OPEN + 3:
  874.     case OPEN + 4:
  875.     case OPEN + 5:
  876.     case OPEN + 6:
  877.     case OPEN + 7:
  878.     case OPEN + 8:
  879.     case OPEN + 9:{
  880.         register int    no;
  881.         register char  *save;
  882.  
  883.         no = OP(scan) - OPEN;
  884.         save = reginput;
  885.  
  886.         if (regmatch(nxt)) {
  887.             /*
  888.              * Don't set startp if some later invocation of the same
  889.              * parentheses already has. 
  890.              */
  891.             if (regstartp[no] == NULL)
  892.             regstartp[no] = save;
  893.             return (1);
  894.         } else
  895.             return (0);
  896.         }
  897.         break;
  898.     case CLOSE + 1:
  899.     case CLOSE + 2:
  900.     case CLOSE + 3:
  901.     case CLOSE + 4:
  902.     case CLOSE + 5:
  903.     case CLOSE + 6:
  904.     case CLOSE + 7:
  905.     case CLOSE + 8:
  906.     case CLOSE + 9:{
  907.         register int    no;
  908.         register char  *save;
  909.  
  910.         no = OP(scan) - CLOSE;
  911.         save = reginput;
  912.  
  913.         if (regmatch(nxt)) {
  914.             /*
  915.              * Don't set endp if some later invocation of the same
  916.              * parentheses already has. 
  917.              */
  918.             if (regendp[no] == NULL)
  919.             regendp[no] = save;
  920.             return (1);
  921.         } else
  922.             return (0);
  923.         }
  924.         break;
  925.     case BRANCH:{
  926.         register char  *save;
  927.  
  928.         if (OP(nxt) != BRANCH)    /* No choice. */
  929.             nxt = OPERAND(scan);    /* Avoid recursion. */
  930.         else {
  931.             do {
  932.             save = reginput;
  933.             if (regmatch(OPERAND(scan)))
  934.                 return (1);
  935.             reginput = save;
  936.             scan = regnext(scan);
  937.             } while (scan != NULL && OP(scan) == BRANCH);
  938.             return (0);
  939.             /* NOTREACHED */
  940.         }
  941.         }
  942.         break;
  943.     case STAR:{
  944.         register char   nextch;
  945.         register int    no;
  946.         register char  *save;
  947.         register int    min;
  948.  
  949.         /*
  950.          * Lookahead to avoid useless match attempts when we know
  951.          * what character comes next. 
  952.          */
  953.         nextch = '\0';
  954.         if (OP(nxt) == EXACTLY)
  955.             nextch = *OPERAND(nxt);
  956.         min = (OP(scan) == STAR) ? 0 : 1;
  957.         save = reginput;
  958.         no = regrepeat(OPERAND(scan));
  959.         while (no >= min) {
  960.             /* If it could work, try it. */
  961.             if (nextch == '\0' || *reginput == nextch)
  962.             if (regmatch(nxt))
  963.                 return (1);
  964.             /* Couldn't or didn't -- back up. */
  965.             no--;
  966.             reginput = save + no;
  967.         }
  968.         return (0);
  969.         }
  970.         break;
  971.     case END:
  972.         return (1);        /* Success! */
  973.         break;
  974.     default:
  975.         regerror("memory corruption");
  976.         return (0);
  977.         break;
  978.     }
  979.  
  980.     scan = nxt;
  981.     }
  982.  
  983.     /*
  984.      * We get here only if there's trouble -- normally "case END" is the
  985.      * terminating point. 
  986.      */
  987.     regerror("corrupted pointers");
  988.     return (0);
  989. }
  990.  
  991. /*
  992.  - regrepeat - repeatedly match something simple, report how many
  993.  */
  994. #ifdef __STDC__
  995.  
  996. static int regrepeat(char *p)
  997.  
  998. #else
  999.  
  1000. static int regrepeat(p)
  1001. char           *p;
  1002.  
  1003. #endif
  1004. {
  1005.     register int    count = 0;
  1006.     register char  *scan;
  1007.     register char  *opnd;
  1008.  
  1009.     scan = reginput;
  1010.     opnd = OPERAND(p);
  1011.     switch (OP(p)) {
  1012.     case ANY:
  1013.     count = strlen(scan);
  1014.     scan += count;
  1015.     break;
  1016.     case EXACTLY:
  1017.     while (*opnd == *scan) {
  1018.         count++;
  1019.         scan++;
  1020.     }
  1021.     break;
  1022.     case ANYOF:
  1023.     while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1024.         count++;
  1025.         scan++;
  1026.     }
  1027.     break;
  1028.     case ANYBUT:
  1029.     while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1030.         count++;
  1031.         scan++;
  1032.     }
  1033.     break;
  1034.     default:            /* Oh dear.  Called inappropriately. */
  1035.     regerror("internal foulup");
  1036.     count = 0;        /* Best compromise. */
  1037.     break;
  1038.     }
  1039.     reginput = scan;
  1040.  
  1041.     return (count);
  1042. }
  1043.  
  1044.  
  1045. /*
  1046.  - regnext - dig the "nxt" pointer out of a node
  1047.  */
  1048. #ifdef __STDC__
  1049.  
  1050. static char *regnext(register char *p)
  1051.  
  1052. #else
  1053.  
  1054. static char *regnext(p)
  1055. register char  *p;
  1056.  
  1057. #endif
  1058. {
  1059.     register int    offset;
  1060.  
  1061.     if (p == ®dummy)
  1062.     return (NULL);
  1063.  
  1064.     offset = NEXT(p);
  1065.     if (offset == 0)
  1066.     return (NULL);
  1067.  
  1068.     if (OP(p) == BACK)
  1069.     return (p - offset);
  1070.     else
  1071.     return (p + offset);
  1072. }
  1073.  
  1074. #ifdef DEBUG
  1075.  
  1076. STATIC char    *regprop();
  1077.  
  1078. /*
  1079.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1080.  */
  1081. #ifdef __STDC__
  1082.  
  1083. void regdump(regexp *r)
  1084.  
  1085. #else
  1086.  
  1087. void regdump(r)
  1088. regexp         *r;
  1089.  
  1090. #endif
  1091. {
  1092.     register char  *s;
  1093.     register char   op = EXACTLY;    /* Arbitrary non-END op. */
  1094.     register char  *nxt;
  1095.     extern char    *strchr();
  1096.  
  1097.  
  1098.     s = r->program + 1;
  1099.     while (op != END) {        /* While that wasn't END last time... */
  1100.     op = OP(s);
  1101.     printf("%2d%s", s - r->program, regprop(s));    /* Where, what. */
  1102.     nxt = regnext(s);
  1103.     if (nxt == NULL)    /* nxt ptr. */
  1104.         printf("(0)");
  1105.     else
  1106.         printf("(%d)", (s - r->program) + (nxt - s));
  1107.     s += 3;
  1108.     if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1109.         /* Literal string, where present. */
  1110.         while (*s != '\0') {
  1111.         putchar(*s);
  1112.         s++;
  1113.         }
  1114.         s++;
  1115.     }
  1116.     putchar('\n');
  1117.     }
  1118.  
  1119.     /* Header fields of interest. */
  1120.     if (r->regstart != '\0')
  1121.     printf("start `%c' ", r->regstart);
  1122.     if (r->reganch)
  1123.     printf("anchored ");
  1124.     if (r->regmust != NULL)
  1125.     printf("must have \"%s\"", r->regmust);
  1126.     printf("\n");
  1127. }
  1128.  
  1129. /*
  1130.  - regprop - printable representation of opcode
  1131.  */
  1132. #ifdef __STDC__
  1133.  
  1134. static char *regprop(char *op)
  1135.  
  1136. #else
  1137.  
  1138. static char *regprop(op)
  1139. char           *op;
  1140.  
  1141. #endif
  1142. {
  1143.     register char  *p;
  1144.     static char     buf[50];
  1145.  
  1146.     strcpy(buf, ":");
  1147.  
  1148.     switch (OP(op)) {
  1149.     case BOL:
  1150.     p = "BOL";
  1151.     break;
  1152.     case EOL:
  1153.     p = "EOL";
  1154.     break;
  1155.     case ANY:
  1156.     p = "ANY";
  1157.     break;
  1158.     case ANYOF:
  1159.     p = "ANYOF";
  1160.     break;
  1161.     case ANYBUT:
  1162.     p = "ANYBUT";
  1163.     break;
  1164.     case BRANCH:
  1165.     p = "BRANCH";
  1166.     break;
  1167.     case EXACTLY:
  1168.     p = "EXACTLY";
  1169.     break;
  1170.     case NOTHING:
  1171.     p = "NOTHING";
  1172.     break;
  1173.     case BACK:
  1174.     p = "BACK";
  1175.     break;
  1176.     case END:
  1177.     p = "END";
  1178.     break;
  1179.     case OPEN + 1:
  1180.     case OPEN + 2:
  1181.     case OPEN + 3:
  1182.     case OPEN + 4:
  1183.     case OPEN + 5:
  1184.     case OPEN + 6:
  1185.     case OPEN + 7:
  1186.     case OPEN + 8:
  1187.     case OPEN + 9:
  1188.     sprintf(buf + strlen(buf), "OPEN%d", OP(op) - OPEN);
  1189.     p = NULL;
  1190.     break;
  1191.     case CLOSE + 1:
  1192.     case CLOSE + 2:
  1193.     case CLOSE + 3:
  1194.     case CLOSE + 4:
  1195.     case CLOSE + 5:
  1196.     case CLOSE + 6:
  1197.     case CLOSE + 7:
  1198.     case CLOSE + 8:
  1199.     case CLOSE + 9:
  1200.     sprintf(buf + strlen(buf), "CLOSE%d", OP(op) - CLOSE);
  1201.     p = NULL;
  1202.     break;
  1203.     case STAR:
  1204.     p = "STAR";
  1205.     break;
  1206.     default:
  1207.     regerror("corrupted opcode");
  1208.     break;
  1209.     }
  1210.     if (p != NULL)
  1211.     strcat(buf, p);
  1212.     return (buf);
  1213. }
  1214. #endif
  1215.  
  1216. /*
  1217.  * The following is provided for those people who do not have strcspn() in
  1218.  * their C libraries.  They should get off their butts and do something
  1219.  * about it; at least one public-domain implementation of those (highly
  1220.  * useful) string routines has been published on Usenet.
  1221.  */
  1222. #ifdef STRCSPN
  1223. /*
  1224.  * strcspn - find length of initial segment of s1 consisting entirely
  1225.  * of characters not from s2
  1226.  */
  1227.  
  1228. #ifdef __STDC__
  1229.  
  1230. static int strcspn(char *s1, char *s2)
  1231.  
  1232. #else
  1233.  
  1234. static int strcspn(s1, s2)
  1235. char           *s1;
  1236. char           *s2;
  1237.  
  1238. #endif
  1239. {
  1240.     register char  *scan1;
  1241.     register char  *scan2;
  1242.     register int    count;
  1243.  
  1244.     count = 0;
  1245.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1246.     for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1247.         if (*scan1 == *scan2++)
  1248.         return (count);
  1249.     count++;
  1250.     }
  1251.     return (count);
  1252. }
  1253. #endif
  1254.  
  1255.  
  1256. /*
  1257.  - regsub - perform substitutions after a regexp match
  1258.  */
  1259. #ifdef __STDC__
  1260.  
  1261. void regsub(regexp *prog, char *source, char *dest)
  1262.  
  1263. #else
  1264.  
  1265. void regsub(prog, source, dest)
  1266. regexp         *prog;
  1267. char           *source;
  1268. char           *dest;
  1269.  
  1270. #endif
  1271. {
  1272.     register char  *src;
  1273.     register char  *dst;
  1274.     register char   c;
  1275.     register int    no;
  1276.     register int    len;
  1277.     extern char    *strncpy();
  1278.  
  1279.     if (prog == NULL || source == NULL || dest == NULL) {
  1280.     regerror("NULL parm to regsub");
  1281.     return;
  1282.     }
  1283.     if (UCHARAT(prog->program) != MAGIC) {
  1284.     regerror("damaged regexp fed to regsub");
  1285.     return;
  1286.     }
  1287.     src = source;
  1288.     dst = dest;
  1289.     while ((c = *src++) != '\0') {
  1290.     if (c == '&')
  1291.         no = 0;
  1292.     else if (c == '\\' && '0' <= *src && *src <= '9')
  1293.         no = *src++ - '0';
  1294.     else
  1295.         no = -1;
  1296.  
  1297.     if (no < 0) {        /* Ordinary character. */
  1298.         if (c == '\\' && (*src == '\\' || *src == '&'))
  1299.         c = *src++;
  1300.         *dst++ = c;
  1301.     } else if (prog->startp[no] != NULL && prog->endp[no] != NULL) {
  1302.         len = prog->endp[no] - prog->startp[no];
  1303.         strncpy(dst, prog->startp[no], len);
  1304.         dst += len;
  1305.         if (len != 0 && *(dst - 1) == '\0') {    /* strncpy hit NUL. */
  1306.         regerror("damaged match string");
  1307.         return;
  1308.         }
  1309.     }
  1310.     }
  1311.     *dst++ = '\0';
  1312. }
  1313.  
  1314.  
  1315. #ifdef __STDC__
  1316.  
  1317. void regerror(char *s)
  1318.  
  1319. #else
  1320.  
  1321. void regerror(s)
  1322. char           *s;
  1323.  
  1324. #endif
  1325. {
  1326. #ifdef NN
  1327.     msg("REGEXP ERROR: %s", s);
  1328. #else    
  1329.     fprintf(stderr, "regexp(3): %s", s);
  1330.     exit(1);
  1331. #endif
  1332. }
  1333.